/*
 * TwoApprDfs.h
 *
 *  Created on: 14 nov. 2011
 *  Authors: bnoleau, cybourdi, rlecrois
 */

#ifndef TWOAPPRDFS_H_
#define TWOAPPRDFS_H_

#define WHITE   0
#define GREY   1
#define BLACK     2

#include "Strategy.h"

class TwoApprDfs: public Strategy {
public:
	TwoApprDfs();
	virtual ~TwoApprDfs();
	virtual list<int> vertexCover(Graph* g);

private:
	Graph* depthSearch(Graph* g);
	bool isColor(Node* n, int color, map<int, int> &nodesColor);
	void markColor(Node* n, int color, map<int, int> &nodesColor);
	list<int> selectNodesExceptEmpty(Graph* g);
};

#endif /* TWOAPPRDFS_H_ */
